package com.jxmobi.util.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

/**
 * 
 * Search target big bytes(byte[]) from source bytes(byte[])<br>
 * <br>
 * This class is going to scan byte[] data in concurrent by using threads, it is
 * effective(means faster speed) in big size(kiloBytes-megaBytes) byte[] data.<br>
 *
 * @author Xiaofei Chen <a href="mailto:neocxf@qq.com">Email the author</a>
 * @version 1.0 12/21/2015
 */
public class BigBinarySearcher extends BinarySearcher {

	// max number of thread
	private static final int DEFAULT_MAX_NUM_OF_THREADS = 128;

	// magic number guided by experiment for my environment.You can change
	// it. :)
	private static final int ANALYZE_BYTE_ARRAY_UNIT_SIZE = 512;

	private int maxNumOfThreads = DEFAULT_MAX_NUM_OF_THREADS;

	/**
	 * Set max number of thread to concurrent access to byte[] data
	 * 
	 * @param maxNumOfThreads
	 */
	public void setMaxNumOfThreads(int maxNumOfThreads) {
		this.maxNumOfThreads = maxNumOfThreads;
	}

	/**
	 * Search bytes faster in a concurrent processing.
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @return
	 */
	public List<Integer> searchBigBytes(byte[] srcBytes, byte[] searchBytes) {

		int numOfThreadsOptimized = (srcBytes.length / ANALYZE_BYTE_ARRAY_UNIT_SIZE);

		if (numOfThreadsOptimized == 0) {
			numOfThreadsOptimized = 1;
		}

		return searchBigBytes(srcBytes, searchBytes, numOfThreadsOptimized);
	}

	/**
	 * Search bytes faster in a concurrent processing with concurrency level.
	 * 
	 * @param srcBytes
	 * @param searchBytes
	 * @param numOfThreads
	 * @return
	 */
	public List<Integer> searchBigBytes(byte[] srcBytes, byte[] searchBytes, int numOfThreads) {

		if (numOfThreads == 0) {
			numOfThreads = 1;
		}

		final int sizeOfSrcBytes = srcBytes.length;
		final int sizeOfSearchBytes = searchBytes.length;

		final int bytesToReadBlockSize = (srcBytes.length - (sizeOfSearchBytes)) / numOfThreads;

		final int threadPoolSize;

		if (maxNumOfThreads == 0) {
			threadPoolSize = numOfThreads;
		} else {
			threadPoolSize = maxNumOfThreads;
		}

		final ExecutorService executorService = Executors.newFixedThreadPool(threadPoolSize);

		final List<Future<List<Integer>>> futureList = new ArrayList<Future<List<Integer>>>();

		for (int i = 0; i < numOfThreads; i++) {

			final int offset = bytesToReadBlockSize * i;
			final int readLeng;

			if (i == numOfThreads - 1) {
				// if it's the last element.
				readLeng = sizeOfSrcBytes - offset - 1;
			} else {
				// else , add the overlapping part size to blockSize
				readLeng = bytesToReadBlockSize + sizeOfSearchBytes;
			}

			final Future<List<Integer>> future = executorService.submit(new BinarySearchTask(srcBytes, searchBytes, offset, readLeng));

			futureList.add(future);
		}
		executorService.shutdown();

		// Remove duplicate indexes
		final List<Integer> resultIndexList = new CopyOnWriteArrayList<Integer>();

		for (Future<List<Integer>> future : futureList) {

			try {
				List<Integer> rawIndexList = future.get();

				for (int i = 0; i < rawIndexList.size(); i++) {

					Integer integer = rawIndexList.get(i);

					if (resultIndexList.contains(integer)) {
						// if already exists , skip
					} else {
						resultIndexList.add(integer);
					}
				}
			} catch (InterruptedException | ExecutionException e) {
			}

		}

		// Sort in ascending order
		resultIndexList.sort((num1, num2) -> {
            if (num1 > num2) {
                return 1;
            } else if (num1 < num2) {
                return -1;
            }
            return 0;
        });

		return resultIndexList;
	}

	class BinarySearchTask implements Callable<List<Integer>> {

		byte[] srcBytes;
		byte[] searchBytes;

		int offset;
		int readLeng;

		BinarySearchTask(byte[] srcBytes, byte[] searchBytes, int offset, int readLeng) {
			this.srcBytes = srcBytes;
			this.offset = offset;
			this.readLeng = readLeng;
			this.searchBytes = searchBytes;
		}

		public List<Integer> call() throws Exception {
			BinarySearcher binSearcher = new BinarySearcher();

			List<Integer> resultIndexList = binSearcher.searchBytes(srcBytes, searchBytes, offset, offset + readLeng);
			return resultIndexList;
		}
	}

}